#include <iostream>

using namespace std;

class Solution {
public:
    int climbStairs(int n)
    {
        // f(x) = f(x-1) + f(x-2),即 x 层台阶只能是从 x-1 或 x-2 爬上
        // r = f(x), p = f(x-1), q = f(x-2)
        // 边界条件 f(0) = 1, f(1) = 1
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

int main()
{
    cout << "Hello World!" << endl;
    return 0;
}
